package competition;

import com.sun.corba.se.spi.presentation.rmi.IDLNameTranslator;

import java.lang.reflect.Array;
import java.util.*;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: competition
 * @Author: 江岸
 * @CreateTime: 2021-03-20 22:31
 * @Description:
 */
public class TwiceWeek48 {
    /**
     * 给你一个混合字符串 s ，请你返回 s 中 第二大 的数字，如果不存在第二大的数字，请你返回 -1 。
     *
     * 混合字符串 由小写英文字母和数字组成。
     * @param s
     * @return
     */
    public int secondHighest(String s) {
        HashSet<Integer> map = new HashSet<>();
        PriorityQueue<Integer> que = new PriorityQueue<>(Comparator.reverseOrder());
        for (int i=0;i<s.length();i++){
            int n =  s.charAt(i)-'0';
            if (n>=0 &&  n<=9){
               if (!map.contains(n)){
                   map.add(n);
                   que.add(n);
               }
            }
        }
        if (map.size()<=1){
            return -1;
        }
        que.poll();
        return que.poll();
    }

    /**
     *
     给你一个长度为 n 的整数数组 coins ，它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。
     如果你从这些硬币中选出一部分硬币，它们的和为 x ，那么称，你可以 构造 出 x 。

     请返回从 0 开始（包括 0 ），你最多能 构造 出多少个连续整数。

     你可能有多个相同值的硬币。
     * @param coins
     * @return
     */
    /**
     * 提示 1
     *
     * 假设数组中若干个元素可以构造出 [0,x]范围内的所有整数。如果此时我们再多选择一个元素 y，那么这些元素可以构造出 [0,x]以及 [y,y+x]范围内的所有整数。
     *
     * 提示 2
     *
     * 如果我们希望这个多选择的元素 y使得答案变得更大，那么区间 [0,x]和 [y,y+x]需要满足什么要求？
     *
     * 思路与算法
     *
     * 由于我们需要从 000 开始构造出尽可能多的连续整数，而不在区间 [0,x] 中的最小整数是 x+1，因此如果 x+1 在区间 [y,y+x] 中，
     * 那么元素 y就会使得构造出的连续整数的范围从 [0,x] 增加到 [0,y+x]；否则，元素 y 不会对答案产生任何影响。
     *
     * 由于数组中的元素都是正整数，那么 x+1≤y+x 恒成立，我们只需要求 y≤x+1 即可保证 x+1  在区间 [y,y+x]  中。
     *
     * 这样一来，我们只需要找出数组中还未被选的元素中最小的那个作为 y即可。如果 y≤x+1，那么就可以更新答案区间，否则剩下更大的元素也不会对答案产生任何影响。
     *
     * 初始时我们没有选择任何元素，对应的区间为 [0,0]。随后我们将数组中的元素升序排序，然后依次判断是否能更新答案区间即可。
     *
     * 作者：zerotrac2
     * 链接：https://leetcode-cn.com/problems/maximum-number-of-consecutive-values-you-can-make/solution/ni-neng-gou-zao-chu-lian-xu-zhi-de-zui-d-hlxf/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param coins
     * @return
     */
    public int getMaximumConsecutive(int[] coins) {
        Arrays.sort(coins);
        int res=0;
        for (int x:coins){
            if (x<=res+1){
                res+=x;
            }else {
                break;
            }
        }
        return res+1;
    }


    /**
     * 给你 nums ，它是一个大小为 2 * n 的正整数数组。你必须对这个数组执行 n 次操作。
     *
     * 在第 i 次操作时（操作编号从 1 开始），你需要：
     *
     *     选择两个元素 x 和 y 。
     *     获得分数 i * gcd(x, y) 。
     *     将 x 和 y 从 nums 中删除。
     *
     * 请你返回 n 次操作后你能获得的分数和最大为多少。
     *
     * 函数 gcd(x, y) 是 x 和 y 的最大公约数。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/maximize-score-after-n-operations
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param
     * @return
     */
    public static void main(String[] args) {


        TwiceWeek48 obj = new TwiceWeek48();
        //9 1 3 1 3
        //2 3 1 3
        //1 5 5
        //1 3
        //5
       //3*9 + 2 * 5 + 1*3 817070 627635/ /817070 712245
        //int i = obj.maxScore(new int[]{481851,31842,817070,452937,627635,712245});
        int i = obj.maxScore(new int[]{481851,31842,817070,452937,627635,712245});
        System.out.println(i);
    }

    public int maxScore(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int x:nums){
            list.add(x);
        }
        List<Integer> path = new ArrayList<>();
        getMaxGcd(list,path);
        //System.out.println(resList);
        int resulet = 0;
        for (int i=nums.length/2;i>0;i--){
            resulet = resulet + i*resList.get(nums.length/2-i);
        }
        return resulet;
    }
    List<Integer> resList ;
    int all = 0;

    public void getMaxGcd(List<Integer> list, List<Integer> path){
        if (list.size()==0){
            System.out.println(path);
            int res=0;
            for (int x:path){
                res+=x;
            }
            if (res>all){
                all = res;
                resList = path;
            }
            return;
        }
        int indexA = 0;
        int indexB = 0;
        int max = 0;
        ArrayList<int[]> arrList = new ArrayList<>();
        for (int i=0;i<list.size()-1;i++){
            for (int j=i+1;j<list.size();j++){
                int gcd = gcd(list.get(i), list.get(j));
                if (gcd>max){
                    arrList.clear();
                    max = gcd;
                    indexA = i;
                    indexB = j;
                    arrList.add(new int[]{i,j});
                }else if (gcd==max){
                    arrList.add(new int[]{i,j});
                }
            }
        }

        if (arrList.size()==1){
            list.remove(indexB);
            list.remove(indexA);
            path.add(max);
            getMaxGcd(list,path);
        }else {
            for (int[] item:arrList){
                ArrayList<Integer> tempList = new ArrayList<>(list);
                ArrayList<Integer> tempPath = new ArrayList<>(path);
                tempList.remove(item[1]);
                tempList.remove(item[0]);
                tempPath.add(max);
                getMaxGcd(tempList,tempPath);
            }
        }
    }

    private  int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

}
class AuthenticationManager {
    int timeToLive;
    HashMap<String,Integer> map;

    public AuthenticationManager(int timeToLive) {
        this.timeToLive = timeToLive;
        map = new HashMap<>();
    }

    public void generate(String tokenId, int currentTime) {
        map.put(tokenId,currentTime+timeToLive);
    }

    public void renew(String tokenId, int currentTime) {
        if (map.get(tokenId)==null || map.get(tokenId)<=currentTime){
            return;
        }
        map.put(tokenId,currentTime+timeToLive);
    }

    public int countUnexpiredTokens(int currentTime) {
        int i=0;
        for (int x:map.values()){
            if (x>currentTime){
                i++;
            }
        }
        return i;
    }
}
